﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;
//9.长度最小的子数组 滑动窗口 
// https://leetcode.cn/problems/minimum-size-subarray-sum/submissions/571430739/
// 手搓混乱代码
//class Solution { 
//public:
//    int minSubArrayLen(int target, vector<int>& nums) {
//        int n = nums.size();
//        if (n == 1 && nums[0] < target) return 0;
//        else if (n == 1 && nums[0] >= target) return 1;
//        int left = 0, right = 1;
//        int len = 10000000;
//        int flag = 0;
//        int sum = nums[0] + nums[1];
//        while (right < n)
//        {
//            if (left == right && sum >= target)
//                return 1;
//            if (sum >= target)
//            {
//                flag = 1;
//                len = min(len, right - left + 1);
//                sum -= nums[left++];
//            }
//            else
//            {
//                if (right == n - 1)
//                    break;
//                sum += nums[++right];
//            }
//        }
//        return flag == 1 ? len : 0;
//    }
//};
//优化代码
//class Solution
//{
//public:
//    int minSubArrayLen(int target, vector<int>& nums)
//    {
//        int n = nums.size(), sum = 0, len = INT_MAX;
//        for (int left = 0, right = 0; right < n; right++)
//        {
//            sum += nums[right]; // 进窗⼝
//            while (sum >= target) // 判断
//            {
//                len = min(len, right - left + 1); // 更新结果
//                sum -= nums[left++]; // 出窗⼝
//            }
//        }
//        return len == INT_MAX ? 0 : len;
//    }
//};
//10.无重复字符的最长子串
//https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/
//class Solution { //手搓 有误
//public:
//    int lengthOfLongestSubstring(string s) {
//        int n = s.size();
//        int left = 0, right = 0;
//        int hash[200] = { 0 };
//        int ret = 0;
//        while (right < n)
//        {
//            hash[s[right]]++;
//            if (hash[s[right]] != 2)
//            {
//                ret = max(ret, right - left + 1);
//            }
//            else
//            {    
//                while (left < right && s[left] != s[right]) left++;
//                left++;
//                if (left == right) 
//                else  hash[s[right]]--;
//                
//            }
//            right++;
//        }
//        return ret;
//    }
//};
//优化代码 窗口
//class Solution
//{
//public:
//    int lengthOfLongestSubstring(string s)
//    {
//        int hash[128] = { 0 }; // 使⽤数组来模拟哈希表
//        int left = 0, right = 0, n = s.size();
//        int ret = 0;
//            while (right < n)
//            {
//                hash[s[right]]++; // 进⼊窗⼝
//                while (hash[s[right]] > 1) // 判断
//                    hash[s[left++]]--; // 出窗⼝ //完美解决出窗口的问题 并且刚好到下一位 代码整洁
//                ret = max(ret, right - left + 1); // 更新结果
//                right++; // 让下⼀个元素进⼊窗⼝
//            }
//        return ret;
//    }
//};
//11.最大连续1的个数 III
//https://leetcode.cn/problems/max-consecutive-ones-iii/description/
//class Solution {
//public:
//    int longestOnes(vector<int>& nums, int k) {
//        int n = nums.size();
//        int count = 0;
//        int len = 0;
//        int left = 0, right = 0;
//        while (right < n)
//        {
//            if (!nums[right])
//                count++;
//            while (count > k)
//                if (nums[left++] == 0) count--;
//            len = max(len, right - left + 1);
//            right++;
//        }
//        return len;
//    }
//};
//12.将x减到0的最小操作数
//https://leetcode.cn/problems/minimum-operations-to-reduce-x-to-zero/description/
// 手搓
//class Solution {
//public:
//    int minOperations(vector<int>& nums, int x) {
//        int n = nums.size();
//        int sum = 0, tmp = 0;
//        for (auto& e : nums)
//            sum += e;
//        int target = sum - x;
//        if (target < 0) return -1;
//        else if (target == 0) return n;
//        int left = 0, right = 0, ret_ = 0;
//        while (right < n)
//        {
//            tmp += nums[right];//进窗口
//            if (tmp == target)
//            {
//                ret_ = max(ret_, right - left + 1);//结果记录
//                right++;
//            }
//            else if (tmp > target)
//            {
//                tmp -= nums[left++];
//                tmp -= nums[right];
//            }
//            else
//                right++;
//        }
//        return ret_==0?-1:n - ret_;
//    }
//};
//优化
class Solution
{
public:
    int minOperations(vector<int>& nums, int x)
    {
        int sum = 0;
        for (int a : nums) sum += a;
        int target = sum - x;
        // 细节问题
        if (target < 0) return -1;
        int ret = -1;
        for (int left = 0, right = 0, tmp = 0; right < nums.size(); right++)
        {
            tmp += nums[right]; // 进窗⼝
            while (tmp > target) // 判断
                tmp -= nums[left++]; // 出窗⼝
            if (tmp == target) // 更新结果
                ret = max(ret, right - left + 1);
        }
        if (ret == -1) return ret;
        else return nums.size() - ret;
    }
};
int main()
{
    vector<int> al{ 1,1,4,2,3 };
    //int ret=Solution().minSubArrayLen(11,al);
    //string s("nfpdmpi");
    //string s("tmmzuxt");
    int ret = Solution().minOperations(al,5);
    cout << ret << endl;
	return 0;
}